﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Gunningine
{
    internal class QuadtreeNode
    {
        private QuadtreeNode[] children = new QuadtreeNode[4];

        private IQuadtreeItem[] items = null;

        Vector3 boundsMin, boundsMax;

        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="items"></param>
        /// <param name="nodeDepth"></param>
        /// <param name="maxDepth"></param>
        /// <param name="maxItemsPerNode"></param>
        public QuadtreeNode(IQuadtreeItem[] items, int nodeDepth, int maxDepth, int maxItemsPerNode)
        {
            // Find bounding volume.
            this.boundsMin = new Vector3(1e10f, 1e10f, 1e10f);
            this.boundsMax = new Vector3(-1e10f, -1e10f, -1e10f);

            foreach (var item in items)
            {
                if (item.BoundsMin.X < this.boundsMin.X)
                    this.boundsMin.X = item.BoundsMin.X;
                if (item.BoundsMin.Y < this.boundsMin.Y)
                    this.boundsMin.Y = item.BoundsMin.Y;
                if (item.BoundsMin.Z < this.boundsMin.Z)
                    this.boundsMin.Z = item.BoundsMin.Z;
                if (item.BoundsMax.X > this.boundsMax.X)
                    this.boundsMax.X = item.BoundsMax.X;
                if (item.BoundsMax.Y > this.boundsMax.Y)
                    this.boundsMax.Y = item.BoundsMax.Y;
                if (item.BoundsMax.Z > this.boundsMax.Z)
                    this.boundsMax.Z = item.BoundsMax.Z;
            }

            // Create child nodes, if we are not at max depth, or
            // we still have enough items.
            if (nodeDepth < maxDepth && items.Length > maxItemsPerNode)
            {
                Vector3 midPoint = this.boundsMin.Lerp(this.boundsMax, 0.5f);
                List<IQuadtreeItem> x0y0 = new List<IQuadtreeItem>();
                List<IQuadtreeItem> x1y0 = new List<IQuadtreeItem>();
                List<IQuadtreeItem> x1y1 = new List<IQuadtreeItem>();
                List<IQuadtreeItem> x0y1 = new List<IQuadtreeItem>();

                // Put all items into child buckets.
                foreach (var item in items)
                {
                    Vector3 itemCentre = item.BoundsMin.Lerp(item.BoundsMax, 0.5f);
                    if (itemCentre.X < midPoint.X)
                    {
                        if (itemCentre.Y < midPoint.Y)
                            x0y0.Add(item);
                        else
                            x0y1.Add(item);
                    }
                    else
                    {
                        if (itemCentre.Y < midPoint.Y)
                            x1y0.Add(item);
                        else
                            x1y1.Add(item);
                    }
                }

                // Create children.
                if (x0y0.Count > 0)
                    children[0] = new QuadtreeNode(x0y0.ToArray(), nodeDepth + 1, maxDepth, maxItemsPerNode);
                if (x1y0.Count > 0)
                    children[1] = new QuadtreeNode(x1y0.ToArray(), nodeDepth + 1, maxDepth, maxItemsPerNode);
                if (x1y1.Count > 0)
                    children[2] = new QuadtreeNode(x1y1.ToArray(), nodeDepth + 1, maxDepth, maxItemsPerNode);
                if (x0y1.Count > 0)
                    children[3] = new QuadtreeNode(x0y1.ToArray(), nodeDepth + 1, maxDepth, maxItemsPerNode);
            }
            else
            {
                this.items = items;
            }
        }

        /// <summary>
        /// Check whether this node is within the clipping planes.
        /// </summary>
        /// <param name="planes"></param>
        /// <returns></returns>
        private bool IsWithinClippingPlanes(Plane[] planes)
        {
            for (int p = 0; p < 6; p++)
            {
                if (planes[p].Normal.X * this.boundsMin.X + planes[p].Normal.Y * this.boundsMin.Y + planes[p].Normal.Z * this.boundsMin.Z + planes[p].Distance > 0)
                    continue;
                if (planes[p].Normal.X * this.boundsMax.X + planes[p].Normal.Y * this.boundsMin.Y + planes[p].Normal.Z * this.boundsMin.Z + planes[p].Distance > 0)
                    continue;
                if (planes[p].Normal.X * this.boundsMin.X + planes[p].Normal.Y * this.boundsMax.Y + planes[p].Normal.Z * this.boundsMin.Z + planes[p].Distance > 0)
                    continue;
                if (planes[p].Normal.X * this.boundsMax.X + planes[p].Normal.Y * this.boundsMax.Y + planes[p].Normal.Z * this.boundsMin.Z + planes[p].Distance > 0)
                    continue;
                if (planes[p].Normal.X * this.boundsMin.X + planes[p].Normal.Y * this.boundsMin.Y + planes[p].Normal.Z * this.boundsMax.Z + planes[p].Distance > 0)
                    continue;
                if (planes[p].Normal.X * this.boundsMax.X + planes[p].Normal.Y * this.boundsMin.Y + planes[p].Normal.Z * this.boundsMax.Z + planes[p].Distance > 0)
                    continue;
                if (planes[p].Normal.X * this.boundsMin.X + planes[p].Normal.Y * this.boundsMax.Y + planes[p].Normal.Z * this.boundsMax.Z + planes[p].Distance > 0)
                    continue;
                if (planes[p].Normal.X * this.boundsMax.X + planes[p].Normal.Y * this.boundsMax.Y + planes[p].Normal.Z * this.boundsMax.Z + planes[p].Distance > 0)
                    continue;

                return false;
            }
            return true;
        }

        /// <summary>
        /// Get items in clipping planes.
        /// </summary>
        /// <param name="planes"></param>
        /// <param name="items"></param>
        public void GetItemsInClippingPlanes(Plane[] planes, List<IQuadtreeItem> items)
        {
            if (IsWithinClippingPlanes(planes))
            {
                if (this.items != null)
                {
                    items.AddRange(this.items);
                }
                else
                {
                    // Check children.
                    for (int i = 0; i < 4; ++i)
                    {
                        if (this.children[i] != null)
                            this.children[i].GetItemsInClippingPlanes(planes, items);
                    }
                }
            }
        }
    }
}
